package 我的Java学习_算法基础.day_03;

import static 我的Java学习_算法基础.day_03._039_最快效率求出乱序数组中第k小的数.selectK;

public class _042_最小可用id是多少_下 {
    public static void main(String[] args) {
        int[] a = {1,2,3,4,6,7};
        int k =findMinID(a);
        System.out.println(k);
    }

    /**
     * 寻找最小可用ID
     * @param array 需要找寻最小ID的数组，数组乱序
     * @return 如果数组元素包含连续的自然数，则返回array.length+1,否则返回空缺的自然数
     */
    public static int findMinID(int[] array){
        return find4(array,0,array.length-1);
    }

    static int find4(int[] array,int l,int r){
        if(l>r){
            return l+1;
        }
        int midIndex = l+((r-l)>>1);
        int q = selectK(array,l,r,midIndex-l+1);//实际在中间位置的值
        int t =midIndex+1;      //期望值
        if(q==t){       //左侧稠密
            return find4(array,midIndex+1,r);
        }else{          //左侧稀疏
            return find4(array,l,midIndex-1);
        }
    }
}
